#include <iostream>
#include <memory.h>
#include <vector>
using namespace std;

vector<int> G[100005];
int n, m, Fmax[100005], Fmin[100005], w[100005];

void dfs(int x, int minx, int last) {
    bool flag = 1;

    minx = min(w[x], minx);
    if (Fmin[x] > minx) {
        Fmin[x] = minx;
        flag = 0;
    }

    int maxx = max(Fmax[last], w[x] - minx);
    if (Fmax[x] < maxx) {
        Fmax[x] = maxx;
        flag = 0;
    }

    if (flag) return;

    for (unsigned i = 0; i < G[x].size(); ++i) {
        dfs(G[x][i], minx, x);
    }
}

int main() {
    int x, y, z;
    cin >> n >> m;
    memset(Fmin, 0x7f, sizeof(Fmin));
    for (int i = 1; i <= n; ++i) cin >> w[i];
    for (int i = 1; i <= m; ++i) {
        cin >> x >> y >> z;
        G[x].push_back(y);
        if(z == 2) G[y].push_back(x);
    }
    dfs(1, 0x7f7f7f7f, 0);
    cout << Fmax[n] << endl;
    return 0;
}